4080. AND Rounds
You are given a cyclic array A having n numbers. In an AND round, each element
of the array A is replaced by the bitwise AND of itself, the previous element,
and the next element in the array. All operations take place simultaneously.
Can you calculate A after k such AND
rounds?
Input. The first line contains the number of test cases t.
Then follow 2t lines, 2 per test
case. The first line contains two space separated integers n (3 ≤ n
≤ 20000) and k (1 ≤ k ≤ 109).
The next line contains n space
separated integers Ai (0 ≤ Ai ≤ 109),
which are the initial values of the elements in array A.
Output. Print t
lines, one per test case. For each test case, output a space separated list of n integers, specifying the contents of
array A after k AND rounds.
Sample
input
2
3
1
1
2 3
5
100
1
11 111 1111 11111
Sample output
0
0 0
1
1 1 1 1
data structures – segment tree
Пусть изначально число Ai
в p-ом бите содержит 0. Тогда после первого раунда числа Ai-1
и Ai+1 в p-ом
бите будут содержать 0 (индексы вычисляются по модулю n). После k-го
раунда числа Ai-1, …, Ai-k
и Ai+1, …, Ai+k
в p-ом бите будут содержать 0.
Если в p-ом бите Ai
изначально находится 0, то;
·
в p-ом
бите Ai ни на каком раунде не появится 1;
·
через k
≥ n / 2 раундов все числа массива в p-ом бите будут
содержать 0.
Лемма. Если k ≥ n / 2, то для решения
задачи достаточно вычислить побитовый AND всех элементов массива и вывести его n
раз. Что и будет ответом.
Лемма. Если k < n / 2, то на Ai
после k раундов подействуют начальные значения Ai-1,
…, Ai-k и Ai+1,
…, Ai+k. Если одно из них в p-ом
бите содержит 0, то после k раундов Ai в в p-ом
бите будет также содержать 0. Значит для ответа на вопрос достаточно вычислить
побитовый AND элементов Ai-k, …, Ai,
…, Ai+k. Это можно совершить за время O(log2n),
если на элементах входного массива A построить дерево отрезков, поддерживающее
операцию побитового AND.
Объявим входной массив а. Дерево отрезков
храним в массиве SegTree.
#define MAX 20010
int a[MAX];
int SegTree[4*MAX];
Построение дерева отрезков, которое
поддерживает битовую операцию AND.
void BuildTree(int *a, int Vertex, int Left,
int Right)
{
if (Left == Right)
SegTree[Vertex] = a[Left];
else
{
int Middle = (Left + Right) / 2;
BuildTree(a, 2*Vertex, Left, Middle);
BuildTree(a, 2*Vertex+1, Middle+1, Right);
SegTree[Vertex] =
SegTree[2*Vertex] & SegTree[2*Vertex+1];
}
}
Вершине Vertex соответствует отрезок [LeftPos, RightPos]. Функция Query возвращает значение aLeft & aLeft+1
& … & aRight.
int Query(int Vertex, int LeftPos, int
RightPos, int Left, int
Right)
{
if (Left > Right) return -1;
if ((Left == LeftPos) && (Right
== RightPos)) return SegTree[Vertex];
int Middle = (LeftPos + RightPos) / 2;
return Query(2*Vertex, LeftPos, Middle,
Left, min(Right,Middle)) &
Query(2*Vertex+1, Middle+1, RightPos,
max(Left,Middle+1),Right);
}
Основная часть программы. Читаем входные
данные в массив а.
scanf("%d",&tests);
while(tests--)
{
scanf("%d %d",&n,&k);
for(i = 0; i < n; i++) scanf("%d",&a[i]);
Если количество раундов k не меньше половины
количества элементов массива, то вычисляем AND всех элементов в переменной res.
if (k >= n / 2)
{
for(res = a[0], i = 1; i < n; i++)
res &= a[i];
Выводим значение res n раз.
for(i = 0; i < n; i++)
{
if (i) printf("
");
printf("%d",res);
}
printf("\n");
continue;
}
Для быстрого ответа на каждый тест построим дерево отрезков
из элементов массива А.
BuildTree(a,1,0,n-1);
Вычисляем значение Ai после k раундов. Оно равно Ai-k
& … & Ai &…& Ai+k.
Индексы элементов вычисляются по модулю n. Если (i – k )
mod n < (i + k) mod n, то достаточно одного запроса на дереве
отрезков. Иначе находим AND элементов от (i – k ) mod n до
n – 1 и от 0 до (i + k) mod n.
for(i = 0; i < n; i++)
{
int Start = (i - k + n) % n;
int End = (i + k + n) % n;
if (Start < End) res =
Query(1,0,n-1,Start,End);
else res = Query(1,0,n-1,Start,n-1)
& Query(1,0,n-1,0, End);
if (i) printf("
");
printf("%d",res);
}
printf("\n");
}